﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode
{
    public class _67AddBinary : IRun
    {
        /*
         * 给定两个二进制字符串，返回他们的和（用二进制表示）。
         * 输入为非空字符串且只包含数字 1 和 0。
         * 示例 1:
         * 输入: a = "11", b = "1"
         * 输出: "100"
         * 示例 2:
         * 输入: a = "1010", b = "1011"
         * 输出: "10101"
         */

        
        /*
         * 解题思路：
         * 1、将a，b长度通过0填充至长度一致；
         * 2、计算a[i]+b[i]+进位数值，计算【新的进位数值】、当前位保留数值；
         *    从右至左进行计算；
         * 3、将计算的数据保留至List<char>中；
         * 4、遍历计算完成后，若【最终进位数值】等于1，则需要扩展一位，数值为1；
         * 5、将List<char>反转后，转成string类型输出；
         */

        public void Run()
        {
            string _Result = AddBinary1("1111","1111");
        }


        public string AddBinary1(string a, string b)
        {
            if (a.Length >= b.Length)
            {
               b = b.PadLeft(a.Length,'0');
            }
            else
            {
               a = a.PadLeft(b.Length, '0');
            }

            List<char> _List = new List<char>();
            int _CarryFlag = 0;
            int _Sum;

            for (int i = a.Length - 1; i >= 0; i--)
            {
                _Sum = _CarryFlag + int.Parse(a[i].ToString()) + int.Parse(b[i].ToString());

                switch (_Sum)
                {
                    case 0:
                        _List.Add('0');
                        _CarryFlag = 0;
                        break;
                    case 1:
                        _List.Add('1');
                        _CarryFlag = 0;
                        break;
                    case 2:
                        _List.Add('0');
                        _CarryFlag = 1;
                        break;
                    case 3:
                        _List.Add('1');
                        _CarryFlag = 1;
                        break;
                }
            }
            if (_CarryFlag == 1)
            {
                _List.Add('1');
            }

            _List.Reverse();
            return new string(_List.ToArray());
        }
    }
}
